#ifndef SORT_H
#define SORT_H
#include <vector>
#include <iostream>
using namespace std;
class Sort{
public:
    static bool comp(int x,int y){
        return x>y;
    }
    void bubble(int arr[],int n,bool (*cmp)(int,int)){
        for(int i=0; i<n-1; i++){
            for(int j=0; j<n-1-i; j++){
                if(cmp(arr[j],arr[j+1])){
                    int t=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=t;
                }
            }
        }
    }

    void bubble_upgrade(int arr[],int n,bool (*cmp)(int,int)){
        int last=n-1,border=last;
        bool changed;
        for(int i=0; i<n-1; i++){
            changed=false;
            for(int j=0; j<border; j++){
                if(cmp(arr[j],arr[j+1])){
                    int t=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=t;
                    last=j;
                    changed=true;
                }
            }
            if(!changed){
                cout<<"already sorted,when i="<<i<<endl;
                break;
            }
            border=last;
        }
    }
    void insert_partition(int arr[],int n,bool (*cmp)(int,int)){
        for(int i=1; i<n; i++){
            int cmping = arr[i];
            int idx=i-1;
            while(idx>=0 && cmp(arr[idx],cmping)){
                arr[idx+1]=arr[idx];
                idx--;
            }
            arr[idx+1]=cmping;
        }
    }

    template<class NT>
    static void select(vector<NT>& collection, bool (*cmp)(NT&, NT&)){
        for(int i=0; i < collection.size(); i++){
            int idx = i;
            for(int j=i+1; j < collection.size(); j++){
                if(cmp(collection[idx], collection[j])){
                    idx = j;
                }
            }
            Sort::swag<NT>(collection[i], collection[idx]);
        }
    }

    void sort_merge(int arr[],int n){
        merge_partition(arr,0,n-1);
    }
    void merge_partition(int arr[],int l, int r){
        if(l>=r)return;

        int m = (r-l)/2 + l;
        merge_partition(arr,l,m);
        merge_partition(arr,m+1,r);

        merge(arr,l,m,r);
    }
    void merge(int arr[],int l,int m,int r){
        int as1=l,ae1=m,as2=m+1,ae2=r;

        int *t = new int[r-l+1];
        int ti=0;
        while(as1<=ae1 && as2<=ae2){
            if(arr[as1] <= arr[as2]){
                t[ti++]=arr[as1++];
            }else{
                t[ti++]=arr[as2++];
            }
        }
        int fs = as1,fe = ae1;
        if(fs>fe){
            fs = as2;
            fe = ae2;
        }
        while(fs<=fe){
            t[ti++] = arr[fs++];
        }
        ti=0;
        for(int i=l; i<=r; i++){
            arr[i] = t[ti++];
        }
        t = 0;
    }

    template<class NT>
    static void swag(NT& i, NT& j){
        NT t = i;
        i = j;
        j = t;
    }
};



#endif